﻿using System.Net.NetworkInformation;
using System.Text;

namespace BaseSortApp
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] bubbleSort = GetInts();
            Console.WriteLine(ConsoleLine(60, "BubbleSort"));
            Console.WriteLine("原始数据:" + string.Join(",", bubbleSort));
            BubbleSort(bubbleSort);
            Console.WriteLine(string.Format("排序结果:{0}", string.Join(",", bubbleSort)));
            Console.WriteLine(ConsoleLine(60, "BubbleSort"));

            int[] selectSort = GetInts();
            Console.WriteLine(ConsoleLine(60, "SelectSort"));
            Console.WriteLine("原始数据:" + string.Join(",", selectSort));
            SelectSort(selectSort);
            Console.WriteLine(string.Format("排序结果:{0}", string.Join(",", selectSort)));
            Console.WriteLine(ConsoleLine(60, "SelectSort"));

            int[] insertSort = GetInts();
            Console.WriteLine(ConsoleLine(60, "InsertSort"));
            Console.WriteLine("原始数据:" + string.Join(",", insertSort));
            InsertSort(insertSort);
            Console.WriteLine(string.Format("排序结果:{0}", string.Join(",", insertSort)));
            Console.WriteLine(ConsoleLine(60, "InsertSort"));

            int[] quickSort = GetInts();
            Console.WriteLine(ConsoleLine(60, "InsertSort"));
            Console.WriteLine("原始数据:" + string.Join(",", quickSort));
            QuickSort(quickSort, 0, quickSort.Length - 1);
            Console.WriteLine(string.Format("排序结果:{0}", string.Join(",", quickSort)));
            Console.WriteLine(ConsoleLine(60, "InsertSort"));

        }

        #region common
        /// <summary>
        /// 数据
        /// </summary>
        /// <returns></returns>
        static int[] GetInts()
        {
            return [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
        }
        /// <summary>
        /// 输出横线
        /// </summary>
        /// <param name="count"></param>
        /// <param name="title"></param>
        /// <returns></returns>
        static string ConsoleLine(int count, string title)
        {
            StringBuilder sb = new();
            int num = count / 2;
            for (int i = 0; i < num; i++)
            {
                sb.Append('-');
            }
            StringBuilder result = new();
            result.Append(sb);
            result.Append(title);
            result.Append(sb);
            return result.ToString();
        }
        #endregion

        #region 冒泡循环
        /// <summary>
        /// 冒泡循环
        /// </summary>
        /// <param name="nums"></param>
        static void BubbleSort(int[] nums)
        {
            int n = nums.Length;
            for (int i = 0; i < n; i++)
            {
                bool flag = false;//有交换数据
                for (int idx = 0; idx < n - i - 1; idx++)
                {
                    if (nums[idx] > nums[idx + 1])
                    {
                        int temp = nums[idx];
                        nums[idx] = nums[idx + 1];
                        nums[idx + 1] = temp;
                        flag = true;
                    }
                }
                //如果flag为false，那说明本轮排序没有交换，数组有序
                if (!flag)
                {
                    break;
                }
            }
        }
        #endregion

        #region 选择排序
        /// <summary>
        /// 选择排序
        /// </summary>
        /// <param name="nums"></param>
        static void SelectSort(int[] nums)
        {
            int n = nums.Length;
            for (int i = 0; i < n; i++)
            {
                //找到最小的元素
                int minIndex = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (nums[j] < nums[minIndex])
                    {
                        minIndex = j;
                    }
                }
                //minIndex就是无序中最小的元素
                //把最小元素和有序的后一个元素交换位置
                int temp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = temp;
            }

        }
        #endregion

        #region 插入排序
        static void InsertSort(int[] nums)
        {
            int n = nums.Length;
            for (int i = 0; i < n - 1; i++)
            {
                //无序的第一个元素
                int curNum = nums[i + 1];
                //有序的最后一个元素
                int idx = i;
                while (idx >= 0 && nums[idx] > curNum)
                {
                    //把有序的元素往后挪一位
                    nums[idx + 1] = nums[idx];
                    idx -= 1;
                }
                nums[idx + 1] = curNum;
            }

        }

        #endregion

        #region 快速排序
        static void QuickSort(int[] nums, int left, int right)
        {
            if (left >= right)
                return;
            //分区 分好区之后基准值的索引
            int pivotIndex = Partition(nums, left, right);
            //左边的区域，left->pivotIndex-1
            QuickSort(nums, left, pivotIndex-1);
            //右边的区域，pivotIndex+1>right
            QuickSort(nums, pivotIndex + 1, right);
        }
        /// <summary>
        /// 获取基准值
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        static int Partition(int[] nums, int left, int right)
        {
            //第一个元素作为基准值
            int pivot = nums[left];
            while (left < right)
            {
                while (left < right && nums[right] > pivot)
                    right--;
                nums[left] = nums[right];
                while (left < right && nums[left] <= pivot)
                    left++;
                nums[right] = nums[left];
            }
            //基准值的正确位置
            nums[right] = pivot;
            //返回基准值
            return left;
        }

        #endregion


    }
}
